[Coding020] Sort - 交换排序

冒泡排序

More coding records

Get the knowledge flowing and circulating! :)

目录

标题：冒泡排序

冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序对$n$$n$个项目需要$O(n^2)$$O(n^2)$的比较次数，且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。

冒泡排序是与插入排序拥有相等的渐近时间复杂度，但是两种算法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要$O(n^2)$$O(n^2)$次交换，而插入排序只要最多$O(n)$$O(n)$交换。冒泡排序的实现通常会对已经排序好的数列拙劣地执行$O(n^2)$$O(n^2)$，而插入排序在这个例子只需要$O(n)$$O(n)$个运算。因此很多现代的算法教科书避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在内部循环第一次执行时，使用一个旗标来表示有无需要交换的可能，也可以把最优情况下的复杂度降低到$O(n)$$O(n)$。在这个情况，已经排序好的数列就无交换的需要。若在每次走访数列时，把走访顺序反过来，也可以稍微地改进效率。有时候称为鸡尾酒排序，因为算法会从数列的一端到另一端之间穿梭往返。

——维基百科

思想

冒泡排序算法的运作如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个。

2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3. 针对所有的元素重复以上的步骤，除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。

Java语言代码实现

​x
1
import java.util.Scanner;
2

3
public class Solution {
4

5
    /**
6
     * 冒泡排序
7
     */
8
    public static void main(String[] args) {
9
        // TODO Auto-generated method stub
10
        Scanner input = new Scanner(System.in);
11

12
        int n = input.nextInt();
13

14
        int[] arr = new int[n];
15

16
        for (int i = 0; i < n; i++) 
17
        {
18
            arr[i] = input.nextInt();
19
        }
20

21
        System.out.println("============");
22

23
        for (int e : arr) 
24
        {
25
            System.out.print(e + " ");
26
        }
27
        System.out.println();
28

29
        Solution b = new Solution();
30
        b.bubbleSort(arr, n);
31

32
        System.out.println("\n============");
33

34
        for (int e : arr) 
35
        {
36
            System.out.print(e + " ");
37
        }
38
        return;
39
    }
40

41
    public void exchange(int[] arr, int i, int j) 
42
    {
43
        int temp = arr[i];
44
        arr[i] = arr[j];
45
        arr[j] = temp;
46
    }
47

48
    public void bubbleSort(int[] arr, int n) 
49
    {
50
        for (int i = 0; i < n - 1; i++) 
51
        {
52
            for (int j = i + 1; j < n; j++) 
53
            {
54
                if (arr[i] > arr[j]) 
55
                {
56
                    System.out.println("arr[i]:" + arr[i]);
57
                    exchange(arr, i, j);
58
                }
59
            }
60
            System.out.println("==========");
61
        }
62
    }
63

64
}
65

66
/*
67
 * test case:
68
10
69
91 32 13 24 55 46 67 88 79 10
70
 */

运行结果

重点代码段解读

Test Case: 91 32 13 24 55 46 67 88 79 10

• 注意arr[i]在每次循环中都是会变的

复杂度

关于冒泡排序的稳定性

趣站分享：在线算法学习